package com.learn.tree;

/**
 * 求解最大搜索二叉子树的大小
 */
public class MaxSearchTree {
    public static class Node {
        private Node left;
        private Node right;
        private int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public static class Info {
        private boolean isAllBST;
        private int max;
        private int min;
        private int maxSubSearchSize;

        public Info(boolean isAllBST, int max, int min, int maxSubSearchSize) {
            this.isAllBST = isAllBST;
            this.max = max;
            this.min = min;
            this.maxSubSearchSize = maxSubSearchSize;
        }
    }

    public int getMaxSearchSize(Node head) {
        return process(head).maxSubSearchSize;
    }

    public Info process(Node head) {
        if (head == null) {
            return null;
        }

        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        int max = head.value;
        int min = head.value;
        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
        }

        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
        }

        int maxSubSearchSize = 0;
        if (leftInfo != null) {
            maxSubSearchSize = Math.max(leftInfo.maxSubSearchSize, maxSubSearchSize);
        }

        if (rightInfo != null) {
            maxSubSearchSize = Math.max(rightInfo.maxSubSearchSize, maxSubSearchSize);
        }

        boolean isAllBST = false;
        //左子树和右子树都是搜索二叉树。且左子树最大值<当前节点<右子树最小值
        if ((leftInfo == null ? true : leftInfo.isAllBST) && (rightInfo == null ? true : rightInfo.isAllBST) && (leftInfo == null ? true : leftInfo.max < head.value && rightInfo == null ? true : rightInfo.min > head.value)) {
            maxSubSearchSize = (leftInfo == null ? 0 : leftInfo.maxSubSearchSize) + (rightInfo == null ? 0 : rightInfo.maxSubSearchSize) + 1;
            isAllBST = true;

        }
        return new Info(isAllBST, max, min, maxSubSearchSize);

    }
}
